package Test;

public class test {
	public static void selectSort(int[] arr, int n)
	{
		int begin = 0, end = n - 1;
		while(begin < end)
		{
			int maxi = begin, mini = begin;
			for(int i=begin; i<=end; i++)
			{
				if(arr[i] > arr[maxi]) maxi = i;
				if(arr[i] < arr[mini]) mini = i;
			}
			int tmp = arr[begin];
			arr[begin] = arr[mini];
			arr[mini] = tmp;
			if(begin == maxi) {
				maxi = mini;
			}
			tmp = arr[end];
			arr[end] = arr[maxi];
			arr[maxi] = tmp;
			end--;
			begin++;
		}
	}
	
	public static void insertSort(int[] arr, int n)
	{
		for(int i=0; i<n-1; i++)
		{
			int end = i;
			int tmp = arr[end+1];
			while(end >= 0)
			{
				if(arr[end] > tmp)
				{
					arr[end+1] = arr[end];
				}
				else 
				{
					break;
				}
				end--;
			}
			arr[end+1] = tmp;
		}
	}
	
	public static void bubbleSort(int[] arr, int n)
	{
		for(int i=0; i<n-1;i ++)
		{
			for(int j=0; j<n-i-1; j++)
			{
				if(arr[j] > arr[j+1])
				{
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
	}
	
	
	public static void quickSort(int[] arr, int left, int right)
	{
		if(left >= right) return;
		int mid = left + (right-left) / 2;
		int k = arr[mid];
		int l = left, c = left, r = right;
		while(c <= r)
		{
			if(arr[c] < k)
			{
				int tmp = arr[c];
				arr[c] = arr[l];
				arr[l] = tmp;
				l++;
				c++;
			}
			else if(arr[c] > k)
			{
				int tmp = arr[c];
				arr[c] = arr[r];
				arr[r] = tmp;
				r--;
			}
			else c++;
		}
		quickSort(arr, left, l-1);
		quickSort(arr, r+1, right);
	}
	
	
	public static void main(String[] args) {
		int[] arr = {3,1,5,7,9,6,10,8,2,4,11,33,22};
		int n = arr.length;
		
		// 插入排序
		//insertSort(arr, n);
		
		// 选择排序
		// selectSort(arr, n);
		
		// 冒泡排序
		// bubbleSort(arr, n);
		
		// 快速排序
		quickSort(arr, 0, n-1);
		
		for(int i=0; i<n; i++) {
			System.out.println(arr[i] + " ");
		}
		
	}
}
